// 以下是暴力解法，超过时间限制

var equal = function (nums, _nums) {
  if (nums.length !== _nums.length) return false;
  for (let index = 0; index < nums.length; index++) {
    if (nums[index] !== _nums[index]) return false;
  }
  return true;
};

var combine = function (numMaps) {
  let ans = [];
  for (const nums of numMaps) {
    for (let k = 1; k < nums.length; k++) {
      const left = nums[k - 1],
        right = nums[k];
      if (left + right === 2) {
        const _ans = [...nums.slice(0, k - 1), 2, ...nums.slice(k + 1)];
        const some = ans.some((item) => equal(item, _ans));
        if (!some) {
          ans.push(_ans);
        }
      }
    }
  }

  return ans;
};

// var climbStairs = function (n) {
//   const bases = Array(n).fill(1);
//   let numMaps = [bases];
//   let ans = [bases];
//   const mid = Math.floor(n / 2);

//   for (const _ of Array(mid)) {
//     numMaps = combine(numMaps);
//     ans.push(...numMaps);
//   }
//   console.log("ans: ", ans);

//   return ans.length;
// };

var climbStairs = function (n) {
  const bases = Array(n).fill(1);
  let numMaps = [bases];
  let ans = 1;
  const mid = Math.floor(n / 2);

  for (const _ of Array(mid)) {
    numMaps = combine(numMaps);
    ans += numMaps.length;
  }

  return ans;
};

const ans = climbStairs(6);
console.log("ans: ", ans);
